package 华为OD机试B卷复用题.进阶题;

import utils.MyUtil;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class HJ43_区间交集 {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner in = new Scanner(new File("src/main/java/华为OD机试B卷复用题/进阶题/input/43.txt"));
        MyUtil.START();
        Solution(in);
        MyUtil.END();
    }

    // 参考 A 卷进阶题 HJ15-16
    static void Solution(Scanner in) {
        // 初始化
        int N = in.nextInt();
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            list.add(new int[] {a, b});
        }
        list.sort(
                (a, b) -> {
                    return a[0] != b[0] ? a[0] - b[0] : a[1] - b[1];
                });
        // 找到所有交集
        List<int[]> combine = new ArrayList<>();
        for (int i = 0; i < list.size(); i++) {
            int[] a = list.get(i);
            for (int j = i + 1; j < list.size(); j++) {
                int[] b = list.get(j);
                if (b[0] <= a[1]) {
                    combine.add(new int[] {b[0], Math.min(a[1], b[1])});
                }
            }
        }
        // 交集进行区间合并
        if (combine.size() == 0) { // 没有交集则直接输出并返回
            System.out.println("None");
            return;
        }

        List<int[]> result = new ArrayList<>();
        int[] first = combine.get(0);
        int left = first[0];
        int right = first[1];
        int maxRight = right;
        for (int i = 1; i < combine.size(); i++) {
            int[] now = combine.get(i);
            if (now[0] > right) {
                right = Math.max(right, maxRight);
                if (now[0] > maxRight) {
                    result.add(new int[] {left, maxRight});
                    left = now[0];
                    right = now[1];
                    maxRight = now[1];
                }
            } else {
                maxRight = Math.max(maxRight, now[1]);
            }
        }
        if (maxRight >= right) {
            result.add(new int[] {left, maxRight});
        }
        // 输出区间
        for (int[] now : result) {
            System.out.println(now[0] + " " + now[1]);
        }
    }
}
